package 算法.leetcode.labuladong.数组和链表;

/**
 * https://leetcode.cn/problems/range-sum-query-immutable/
 *
 * @author lchenglong
 * @date 2022/6/15
 */
public class 区域和检索_数组不可变 {

    public static void main(String[] args) {
        int[] nums = new int[]{-2, 0, 3, -5, 2, -1};
        NumArray numArray = new NumArray(nums);
        int ans = numArray.sumRange(0, 5);
        System.out.println(ans);

    }

    static class NumArray {
        int[] preSums;

        public NumArray(int[] nums) {
            // 前缀和数组,preNums[0]=0,第一个留空
            preSums = new int[nums.length+1];
            for (int i=1;i<=nums.length;i++){
                preSums[i] = preSums[i-1]+nums[i-1];
            }
        }

        public int sumRange(int left, int right) {
            // 前缀差==区域数组和
            return preSums[right+1]-preSums[left];
        }
    }
}
